#include<bits/stdc++.h>
using namespace std;

class Solution {
public:
    vector<int> pancakeSort(vector<int>& arr) {
        vector<int>ans;
        for(int i = arr.size(); i > 0; i--){
            if(arr[i - 1] == i)continue;
            for(int j = 0; j < i; j++){
                if(arr[j] == i){
                    reverse(arr.begin(), arr.begin() + j + 1);
                    ans.push_back(j + 1);
                    break;
                }
            }
            reverse(arr.begin(), arr.begin() + i);
            ans.push_back(i);
        }
        return ans;
    }
};
/**
 * @brief 2022.2.19
 * 最快的方法也就是 O(n^2)了...本来以为这个方法够慢的迟迟不敢写
 * 每个数字分成三步，第一步找到未排序数组中最大的数，第二步将该数
 * 及前面的数翻转，再将整个未排序数组翻转，该数就到了为排序数组的
 * 最后了，再依次往前执行上述步骤即可。
 */